/**
 * @Author Fizz Pu
 * @Date 2020/9/27 下午9:48
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
 *
 * 任何左括号 ( 必须有相应的右括号 )。
 * 任何右括号 ) 必须有相应的左括号 ( 。
 * 左括号 ( 必须在对应的右括号之前 )。
 * * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
 * 一个空字符串也被视为有效字符串。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parenthesis-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Lee678 {
    public static void main(String[] args) {
        Lee678 lee678 = new Lee678();
        System.out.println(lee678.checkValidString("()()((()())((()))(*"));
    }

    public boolean checkValidString(String s) {
       Deque<Character> mainStack = new LinkedList<>();
       Deque<Character> supStack = new LinkedList<>();
        for(int i = 0; i < s.length(); ++i){
            char ch = s.charAt(i);
            if(ch == '('){
                mainStack.push(ch);
            }else if(ch == ')'){
                if(!mainStack.isEmpty())mainStack.pop();
                else {
                    if(supStack.isEmpty())return false;
                    else supStack.pop();
                }
            } else  if(ch == '*'){
                supStack.push(ch);
            }
        }
       while(!mainStack.isEmpty() && !supStack.isEmpty()){
           mainStack.pop();
           supStack.pop();
       }
       return mainStack.isEmpty();
        /* List<Integer> count = count(s);
        int num = 0;
        int gap = count.get(0)-count.get(1);
        if(Math.abs(gap) > count.get(2)){
            return false;
        }
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < s.length(); ++i){
            char  ch = s.charAt(i);
            if(ch == '*') {
                num++;
                if (gap > 0 && num <= Math.abs(gap)) {
                    ch = ')';
                } else if (gap == 0 || num > Math.abs(gap)) {
                    ch = ' ';
                } else if (gap < 0 && num <= Math.abs(gap)) {
                    ch = '(';
                }
            }
            if(ch == '(')stack.push(ch);
            else if(ch == ')' && !stack.isEmpty())stack.pop();
            else if (ch == ')' && stack.isEmpty())return false;
            }
        return stack.isEmpty();*/
    }

    // 统计左右括号的个数
    // 下标为0当作左括号个数
    // 下标为1当作右括号个数
    // 下标为2当作*的个数
    /*List<Integer> count(String s){
        List<Integer> res = new ArrayList<>(2);
        res.add(0);
        res.add(0);
        res.add(0);
        for(int i = 0; i < s.length(); ++i){
            if(s.charAt(i) == '('){
                res.set(0,res.get(0)+1);
            }
            else if(s.charAt(i) == ')'){
                res.set(1,res.get(1)+1);
            }
            else if(s.charAt(i) == '*'){
                res.set(2,res.get(2)+1);
            }
        }
        return res;
    }*/
}

